import java.util.PriorityQueue;

public class SolutionInterview17_20 {

    PriorityQueue<Integer> queue1=new PriorityQueue<>((a, b) -> (b - a));
    PriorityQueue<Integer> queue2=new PriorityQueue<>((a, b) -> (a - b));

    public SolutionInterview17_20() {

    }

    public void addNum(int num) {
        if (queue1.isEmpty()||num<=queue1.peek()){
            queue1.offer(num);
            if (queue1.size()>queue2.size()+1){
                queue2.offer(queue1.poll());
            }
        }else{
            queue2.offer(num);
            if (queue1.size()<queue2.size()){
                queue1.offer(queue2.poll());
            }
        }
    }

    public double findMedian() {
        if (queue1.size()>queue2.size()){
            return queue1.peek();
        }else{
            return (queue1.peek()+queue2.peek())/2.0;
        }
    }

    public static void main(String[] args) {
        SolutionInterview17_20 solutionInterview17_20=new SolutionInterview17_20();
        solutionInterview17_20.addNum(1);
        solutionInterview17_20.addNum(2);
        System.out.println(solutionInterview17_20.findMedian());
        solutionInterview17_20.addNum(3);
        System.out.println(solutionInterview17_20.findMedian());
    }
}
